home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 7817 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.8 KB
  1. Path: newshub.alcatel.no!STKT22
  2. From: Sven.Pran@alcatel.no (Sven Pran)
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: Mon, 19 Feb 96 12:44:09 GMT
  6. Organization: Alcatel Network Services, Norway
  7. Message-ID: <4g9rpt$41o@gatekeeper.alcatel.no>
  8. References: <4fr8be$ass@news.iconn.net> <4g0giv$94s@sun132.spd.dsccc.com>
  9. NNTP-Posting-Host: stkt22.alcatel.no
  10. X-Newsreader: News Xpress Version 1.0 Beta #4
  11.  
  12. In article <4g0giv$94s@sun132.spd.dsccc.com>,
  13.    kcline@sun132.spd.dsccc.com (Kevin Cline) wrote:
  14. >In article <4fr8be$ass@news.iconn.net>, The Crow <thecrow@iconn.net> wrote:
  15. >>Here is what I am trying to do, I want to find the last NON-ZERO digit of a
  16. >>given factorial.  For instance,
  17. >>
  18. >>5! = 120
  19. >>
  20. >>so the last non-zero digit is 2.  I want to be able to do this up to 1000.
  21. >>Problem is, no matter how huge of a data-type you use, there isn't any way 
  22. for
  23. >>the computer to handle 1000!, it is however possible to find the last 
  24. non-zero
  25. >>digit somehow.  One thing I have tried is as I went through mulitplying the
  26. >>series of numbers in the factorial (5 * 4 * 3 * 2) I would remove all the
  27. >>trailing ZEROS, I got this to work up to 789, but it wont work with 1000 and 
  28. i
  29. >>am not really sure why.  If anyone has a clue how I can do this let me know.
  30. >>
  31. >>--
  32. >
  33. >Since so many people have produced an incorrect solution to this problem,
  34. >I thought it would be worthwhile posting the correct solution.
  35. >
  36. >Everyone had the right idea, which is to keep only the last digit
  37. >and compute the change when multiplying by the next number
  38. >in the factorial, but couldn't figure out what to do
  39. >about the numbers that end in 5, since that introduces a new zero
  40. >in the series.  The answer is simple; when multiplying by five,
  41. >take half of the previous digit +-5 to make an even number.
  42.  
  43. This was a major step towards the correct solution, but alas still incorrect!
  44.  
  45. Look what happens when the multiplier ends in 25 or 75 (producing 2 zeroes), 
  46. and even worse when the multiplier is 125 (producing 3 zeroes) and finally 
  47. 625 (producing 4 zeroes).
  48.  
  49. So what is the correct solution? Simple when I finally stumbled across it:
  50.  
  51. Don't use up the multipliers entirely in the process, but save some factors 2
  52. sufficient in number to match one such factor 2 with each factor 5 whenever a
  53. multiplier divisible by 5 is to be processed! Such couples are then discarded 
  54. before performing the multiplication.
  55.  
  56. Example:
  57. RSD(4) = 1 * 2 * 3 * 4 = 4    (discarding the leading 2 in the product)
  58. RSD(5) = 1 * 2 * 3 * 2 (!) * (2*5) = 2 (discarding the factor 2*5 etc.)
  59. RSD(6) = 2 * 6 = 2
  60. RSD(7) = 2 * 7 = 4
  61.  . .
  62. RSD(23) = 2 (I hope I calculated this one correct)
  63. RSD(24) = 2 * 24 = 8
  64. RSD(25) = 2 * 6 (!) * (4 * 25) = 2    (discarding the factor 4*25 etc.)
  65.  
  66. and so on.
  67.  
  68. Eureka ! (?)
  69.  
  70. Sven
  71.